package basic.study.leetcode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName Hard297
 * @Description 二叉树的序列化和反序列化
 * @Company inspur
 * @Author Kevin
 * @Date 2020/7/12 9:40
 * @Version 1.0
 */
public class Hard297 {

    public class Codec {
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if(root==null) return new String();
            StringBuilder result=new StringBuilder();
            result.append('[');
            Deque<TreeNode> quque=new LinkedList<>();
            quque.add(root);
            TreeNode cur;
            int validNum=1;//此时队列非空结点为1
            while(validNum!=0){
                cur=quque.remove();
                if(cur!=null){
                    validNum--;//非空结点-1
                    result.append(cur.val);
                    result.append(',');
                    if(cur.left!=null){
                        quque.add(cur.left);
                        validNum++;//非空结点+1
                    }
                    else quque.add(null);
                    if(cur.right!=null){
                        quque.add(cur.right);
                        validNum++;//非空结点+1
                    }
                    else quque.add(null);
                }
                else result.append("null,");
            }
            result.setLength(result.length() - 1);//去掉最后一个逗号
            result.append(']');
            return result.toString();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if(data.length()<3) return null;
            String[] convertedData=data.substring(1,data.length()-1).split(",");
            TreeNode root= new TreeNode(Integer.valueOf(convertedData[0]));
            Deque<TreeNode> quque=new LinkedList<>();
            quque.add(root);
            TreeNode cur;
            int idx=0;
            while(true){
                cur=quque.remove();
                if(++idx>=convertedData.length) break;
                if(convertedData[idx].compareTo("null")!=0) {
                    cur.left=new TreeNode(Integer.valueOf(convertedData[idx]));
                    quque.add(cur.left);
                }
                if(++idx>=convertedData.length) break;
                if(convertedData[idx].compareTo("null")!=0) {
                    cur.right=new TreeNode(Integer.valueOf(convertedData[idx]));
                    quque.add(cur.right);
                }
            }
            return root;
        }
    }


    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            this.val = x;
        }
    }
}
